import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 先检查 endWord 在不在 wordList 中
        Set<String> wordListSet = new HashSet<>();
        for(String word : wordList){
            wordListSet.add(word);
        }
        if(!wordListSet.contains(endWord)){
            return 0;
        }
        // 创建标记用的 set
        Set<String> mark = new HashSet<>();

        int ret = 1;
        int len = beginWord.length();
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        mark.add(beginWord);
        while(!queue.isEmpty()){
            int size = queue.size();
            ret++;
            // 枚举一次变化的所有可能
            while(size > 0){
                String word = queue.poll();
                // 进行单词变化
                for(int i = 0; i < len; i++){
                    char[] wordArray = word.toCharArray();
                    for(int j = 0; j < 26; j++){
                        wordArray[i] = (char)('a' + j);
                        String changedWord = new String(wordArray);
                        if(wordListSet.contains(changedWord) && !mark.contains(changedWord)){
                            if(changedWord.equals(endWord)){
                                return ret;
                            }
                            queue.offer(changedWord);
                            mark.add(changedWord);
                        }
                    }
                }
                size--;
            }
        }
        return 0;
    }
}